#include<stdio.h>
//typedef struct ListNode ListNode;
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        ListNode* pcur = pHead;
//        ListNode* SmallHead = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* BigHead = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* sh = SmallHead, * bh = BigHead;
//        while (pcur)
//        {
//            if (pcur->val < x)
//            {
//                sh->next = pcur;
//                sh = sh->next;
//                pcur = pcur->next;
//            }
//            else {
//                bh->next = pcur;
//                bh = bh->next;
//                pcur = pcur->next;
//            }
//        }
//        sh->next = BigHead->next;
//        ListNode* ret = SmallHead->next;
//        free(SmallHead);
//        free(BigHead);
//        SmallHead = BigHead = bh->next = NULL;
//        return ret;
//    }
//};

//typedef struct ListNode ListNode;
//class Solution {
//public:
//    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
//        ListNode* pa = headA;
//        ListNode* pb = headB;
//        int sizea = 0, sizeb = 0;
//        while (pa)
//        {
//            ++sizea;
//            pa = pa->next;
//        }
//        while (pb)
//        {
//            ++sizeb;
//            pb = pb->next;
//        }
//        int gap = abs(sizea - sizeb);
//        ListNode* chang = headA;
//        ListNode* duan = headB;
//        if (sizeb > sizea)
//        {
//            chang = headB, duan = headA;
//        }
//        while (gap--)
//        {
//            chang = chang->next;
//        }
//        while (chang)
//        {
//            if (chang == duan)
//                return chang;
//            chang = chang->next;
//            duan = duan->next;
//        }
//        return NULL;
//    }
//};
//typedef struct ListNode ListNode;
//class Solution {
//public:
//    bool hasCycle(ListNode* head) {
//        ListNode* fast = head, * slow = head;
//        while (fast && fast->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//            if (fast == slow)
//                return true;
//        }
//        return false;
//    }
//};

//typedef struct ListNode ListNode;
//class Solution {
//public:
//    ListNode* detectCycle(ListNode* head) {
//        ListNode* slow, * fast, * pcur;
//        slow = fast = pcur = head;
//        while (fast && fast->next && fast->next->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//            if (fast == slow)
//            {
//                while (slow != pcur)
//                {
//                    slow = slow->next;
//                    pcur = pcur->next;
//                }
//                return pcur;
//            }
//        }
//        return NULL;
//    }
//};